package com.banmao.CarlCamp.Day08;

import com.alibaba.fastjson.JSON;

/**
 *  前缀表第二种形式
 *  整体右移一位，首位补-1
 */
public class KMP_2 {

    private static int[] getNext(char[] needleChars) {
        if (needleChars.length <= 1) {
            return new int[] {-1};
        }

        // 第二种形式，整体右移一位，首位补-1
        // 生成 next 数组
        int[] next = new int[needleChars.length];
        // 1. 初始化
        next[0] = -1;
        next[1] = 0;
        // j 指向前缀的尾字符
        int j = 0;
        // i 指向后缀的尾字符，从 1 开始
        for (int i = 1; i < needleChars.length - 1; i++) {
            // 2. 处理前后缀不相同的情况
            while (j > 0 && needleChars[i] != needleChars[j]) {
                j = next[j];
            }
            // 3. 处理前后缀相同的情况
            if (needleChars[i] == needleChars[j]) {
                j++;
            }
            next[i + 1] = j;
        }
        return next;
    }

    public static int strStr(String haystack, String needle) {

        int[] next = getNext(needle.toCharArray());

        // i为文本串指针，j为模式串指针
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length()) {
                return i - j + 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {

        System.out.println(JSON.toJSONString(getNext("aabaaac".toCharArray())));

        int res = strStr("aabaaabaaac", "ss");
        System.out.println(res);

    }

}
